package Niuke;

/**
 * @author leiwenkang <leiwenkang@kuaishou.com>
 * Created on 2022-07-28
 */
public class Test145背包问题 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,3},{10,4}};
        System.out.println(knapsack2(10, 2, matrix));
    }

    public static int knapsack (int V, int n, int[][] vw) {
        //dp[i][j] 表示i个物品，体积为j情况下，最多可以容纳的重量
        int[][] dp = new int[n + 1][V + 1];

        //转移方程
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if (vw[i - 1][0] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][V];
    }

    public static int knapsack2(int V, int n, int[][] vw) {
        // write code here
        int[] dp = new int[V+1];
        for(int i = 1; i<=n;i++){
            for(int j = V;j>=1;j--){
                if(j>vw[i-1][0]){
                    dp[j] = Math.max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1]);
                }
            }
        }
        return dp[V];
    }
}
